# Definition for a binary tree node.
from typing import List, Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def setChild(io: List[int], po: List[int]):
            if not io or not po: return None
            # 在中序遍历中分离出左右子树
            for i, val in enumerate(io):
                if val == po[-1]:
                    break
            # i 即为根的索引 也为左子树的节点个数
            node = TreeNode(val)
            left = setChild(io[:i], po[:i])
            right = setChild(io[i + 1:], po[i:-1])
            node.left = left
            node.right = right
            return node

        return setChild(inorder, postorder)


if __name__ == '__main__':
    s = Solution()
    r = s.buildTree(inorder=[9, 3, 15, 20, 7], postorder=[9, 15, 7, 20, 3])
    print(r)
